home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d13 / ptv2n1.arc / L5.ASM < prev    next >
Assembly Source File  |  1991-03-26  |  3KB  |  88 lines
  1. ; Finds and returns the greatest common divisor of two integers.
  2. ; Uses Euclid's Algorithm: divides the larger integer by the
  3. ; smaller; if the remainder is 0, the smaller integer is the gcd,
  4. ; otherwise the smaller integer becomes the larger integer, the
  5. ; remainder becomes the smaller integer, and the process is
  6. ; repeated. Avoids code recursion.
  7. ;
  8. ; Tested with MASM 5.1.
  9. ;
  10. ; C near-callable as:
  11. ;        unsigned int gcd(unsigned int int1, unsigned int int2);
  12.  
  13. ; Parameter structure:
  14. parms    struc
  15.     dw    ?        ;pushed BP
  16.     dw    ?        ;pushed return address
  17. int1    dw    ?        ;integers for which to find
  18. int2    dw    ?        ; the gcd
  19. parms    ends
  20.  
  21.     .model    small
  22.     .code
  23.     public    _gcd
  24.     align    2
  25. _gcd    proc    near
  26.     push    bp    ;preserve caller's stack frame
  27.     mov    bp,sp    ;set up our stack frame
  28.     push    si    ;preserve caller's register variables
  29.     push    di
  30.  
  31. ;Swap if necessary to make sure that int1 >= int2
  32.     mov    ax,int1[bp]
  33.     mov    bx,int2[bp]
  34.     cmp    ax,bx        ;is int1 >= int2?
  35.     jnb    IntsSet        ;yes, so we're all set
  36.     xchg    ax,bx        ;no, so swap int1 and int2
  37. IntsSet:
  38.  
  39. ; Now loop, dividing int1 by int2 and checking the remainder, until
  40. ; the remainder is 0. At each step, if the remainder isn't 0, assign
  41. ; int2 to int1, and the remainder to int2, then repeat.
  42. GCDLoop:
  43.                 ;if the remainder of int1 divided by
  44.                 ; int2 is 0, then int2 is the gcd
  45.     sub    dx,dx        ;prepare int1 in DX:AX for division
  46.     div    bx        ;int1/int2; remainder is in DX
  47.     and    dx,dx        ;is the remainder zero?
  48.     jz    Done        ;yes, so int2 (BX) is the gcd
  49.                 ;no, so move int2 to int1 and the
  50.                                 ; remainder to int2, and repeat the
  51.                                 ; process
  52.     mov    ax,bx        ;int1 = int2;
  53.     mov    bx,dx        ;int2 = remainder from DIV
  54.  
  55. ;---start of loop unrolling; the above is repeated three times---
  56.     sub    dx,dx        ;prepare int1 in DX:AX for division
  57.     div    bx        ;int1/int2; remainder is in DX
  58.     and    dx,dx        ;is the remainder zero?
  59.     jz    Done        ;yes, so int2 (BX) is the gcd
  60.     mov    ax,bx        ;int1 = int2;
  61.     mov    bx,dx        ;int2 = remainder from DIV
  62. ;---
  63.     sub    dx,dx        ;prepare int1 in DX:AX for division
  64.     div    bx        ;int1/int2; remainder is in DX
  65.     and    dx,dx        ;is the remainder zero?
  66.     jz    Done        ;yes, so int2 (BX) is the gcd
  67.     mov    ax,bx        ;int1 = int2;
  68.     mov    bx,dx        ;int2 = remainder from DIV
  69. ;---
  70.     sub    dx,dx        ;prepare int1 in DX:AX for division
  71.     div    bx        ;int1/int2; remainder is in DX
  72.     and    dx,dx        ;is the remainder zero?
  73.     jz    Done        ;yes, so int2 (BX) is the gcd
  74.     mov    ax,bx        ;int1 = int2;
  75.     mov    bx,dx        ;int2 = remainder from DIV
  76. ;---end of loop unrolling---
  77.     jmp    GCDLoop
  78.  
  79.     align    2
  80. Done:
  81.     mov    ax,bx        ;return the gcd
  82.     pop    di        ;restore caller's register variables
  83.     pop    si
  84.     pop    bp        ;restore caller's stack frame
  85.     ret
  86. _gcd    endp
  87.     end
  88.